/**
 * 给定大写字母字符串S，在其中任意位置插入任意一个大写字母，
 * 使得修改过后的字符串含有最多的子序列“LCT”
 * 首先基于贪心的思想，显然只有三个候选字母。
 * 其次基于贪心的思想，'L'显然只需要插入到开头，而'T'需要插入到结尾
 * 至于'C'可能插入到中间，其可能增加的数量显然是左边L的数量乘以右边T的数量，
 * 因此做一个计数即可。
 * 至于给定字符串求子序列的数量，用DP或者递推均可完成。
 */
class Solution {
using vi = vector<int>;
using llt = long long;

vi L, C, T;
public:
    long long numOfSubsequences(string s) {
        llt ans = 0;
        ans = max(ans, dp(string(1, 'L') + s));
        ans = max(ans, dp(s + string(1, 'T')));
        ans = max(ans, proc(s) + dp(s));
        return ans;
    }

    llt dp(const string & s){
        llt ret = 0;
        llt a = 0, b = 0;
        for(auto c : s){
            if('L' == c){
                a += 1;
            }else if('C' == c){
                b += a;
            }else if('T' == c){
                ret += b;
            }
        }
        return ret;
    }

    llt proc(const string & s){
        int n = s.length();
        vi a(n, 0), b(n, 0);
        a[0] = s[0] == 'L' ? 1 : 0;
        for(int i=1;i<n;++i){
            a[i] = a[i - 1];
            if('L' == s[i]) a[i] += 1;
        }
        b[n - 1] = 'T' == s[n - 1] ? 1 : 0;
        for(int i=n-2;i>=0;--i){
            b[i] = b[i + 1];
            if('T' == s[i]) b[i] += 1;
        }
        
        llt ret = 0;
        for(int i=1;i<n;++i){
            ret = max(ret, (llt)a[i - 1] * b[i]);
        }
        return ret;
    }
};